/*
 * @lc app=leetcode.cn id=790 lang=typescript
 *
 * [790] 多米诺和托米诺平铺
 */

// @lc code=start
function numTilings(n: number): number {
  if (n === 1) return 1;
  const mod = 1e9 + 7;
  const f: number[] = new Array(n + 1).fill(0);
  f[0] = f[1] = 1;
  f[2] = 2;
  for (let i = 3; i <= n; i++) {
    f[i] = (f[i - 1] * 2 + f[i - 3]) % mod;
  }
  return f[n];
}
// @lc code=end
